package com.darrenchan.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-19 00:39
 */
public class Q922 {
    public int[] sortArrayByParityII(int[] A) {
        int[] res = new int[A.length];
        Queue<Integer> odd = new LinkedList<>();
        Queue<Integer> even = new LinkedList<>();

        for (int i = 0; i < A.length; i++) {
            if((A[i] & 1) == 1){
                odd.add(A[i]);
            }else{
                even.add(A[i]);
            }
        }

        for (int i = 0; i < A.length; i++) {
            if((i & 1) == 1){
                res[i] = odd.poll();
            } else {
                res[i] = even.poll();
            }
        }
        return res;
    }

    public int[] sortArrayByParityII2(int[] A) {
        if(A == null || A.length == 0) {
            return A;
        }

        int i = 0, j = A.length - 1;
        while (i <= j) {
            while (i <= j && A[i] % 2 == 0) {
                i++;
            }

            while (i <= j && A[j] % 2 == 1) {
                j--;
            }

            if(i <= j) {
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;

                i++;
                j--;
            }
        }

        i = 1;
        j = A.length - 2;
        while (i < j) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;

            i += 2;
            j -= 2;
        }

        return A;
    }
}
